package com.bblei.demo.leetcode;

public class LeetCodeTop_2 {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
    //这个方法有效地将两个以链表形式表示的数字逐位相加，考虑到每次加法的进位。
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //carry变量用于存储两个数字相加后的进位值。
        int carry = 0;
        //创建一个虚拟节点作为新链表的头节点.虚拟节点的值设置为 0，因为在相加过程中可能会产生进位，需要一个额外的节点来保存进位的值。
        ListNode dummy = new ListNode(0);
        //pre节点用于跟踪新链表的最后一个节点.初始时，pre 指向虚拟节点(dummy)。
        // 在循环迭代过程中，每次都将新节点添加到 pre 的后面，然后将 pre 更新为新节点，
        // 以便继续跟踪新链表的最后一个节点。这样可以确保在循环结束后，pre 指向新链表的最后一个节点。
        ListNode pre = dummy;
        //只要输入链表中还有节点或者有进位值，while循环就会继续
        while (l1 != null || l2 != null || carry == 1) {
            // 用于创建一个新节点，并将其添加到新链表中。
            // 首先，创建一个值为 carry 的新节点，并将其赋给 pre 的下一个节点，
            // 即当前新链表的最后一个节点的下一个节点。然后，将 pre 更新为这个新节点，
            // 以便在下一次迭代时继续添加新的节点到新链表的末尾。
            // 这样做可以确保每次迭代后，pre 始终指向新链表的最后一个节点。
            pre.next = new ListNode(carry);
            pre = pre.next;
            //接下来的if语句检查输入链表中是否还有节点。
            //如果有，就将当前节点的值加到新节点的值上，并将指针移动到下一个节点。
            if (l1 != null) {
                //累加l1的值
                pre.val += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                pre.val += l2.val;
                l2 = l2.next;
            }
            //值相加后，通过将新节点的值除以10来计算下一次迭代的进位值。
            //然后将新节点的值更新为除以10的余数。
            carry = pre.val / 10;
            pre.val %= 10;
        }
        //最后，循环结束后，方法返回虚拟节点的下一个节点，
        // 这是代表两个输入数字之和的新链表的头节点
        return dummy.next;
    }


    public static void main(String[] args) {
        //https://leetcode.cn/problems/add-two-numbers/description/?envType=study-plan-v2&envId=top-100-liked
        //给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
        //
        //请你将两个数相加，并以相同形式返回一个表示和的链表。
        //
        //你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
        //在这个问题中，两个非负整数分别以逆序方式存储在两个链表中。这意味着，每个链表的第一个节点包含最低位上的数字，
        // 第二个节点包含次低位上的数字，以此类推。
        // 例如，对于数字 342，链表的表示为 2 -> 4 -> 3，其中每个节点分别代表数字的个位、十位和百位。
        //同样地，对于数字 465，链表的表示为 5 -> 6 -> 4，其中每个节点分别代表数字的个位、十位和百位。

        //是按照位（一个数字的 个 十 百 千 ）由低到高进行存储的
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);

        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);

        ListNode listNode = addTwoNumbers(l1, l2);
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }

    }
}
